package main.java.huaweiOD;

import org.apache.commons.lang3.StringUtils;

/**
 * Project: tobe-better-coder
 * Package: huaweiOD
 *
 * @author : Mr.xu
 * @date : 2023/5/11 8:31
 */
public class IsInterleave {

    public static void main(String[] args) {
        IsInterleave isInterleave = new IsInterleave();
        System.out.println(isInterleave.solution("", "11", "11"));
    }

    public boolean solution(String s1,String s2,String s3){
        if (s1 == null || s2 == null || s3 == null || (s1.length() +s2.length() != s3.length())) {
            return false;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] str3 = s3.toCharArray();
        // 动态规划的样本对应模型：
        int[][] dp = new int[str1.length + 1][str2.length + 1];
        // 一个都不选，那么一定能搞出一个空串
        dp[0][0] = 1;
        // 填第一列，也就是只选用str1中的字符
        for (int i = 1; i <= str1.length; i++) {
            // 如果有一个不满足，那么后续的串就都不能拼出str3
            if (str1[i - 1] != str3[i - 1]) {
                break;
            }
            dp[i][0] = 1;
        }
        // 填第一行，也就是只选用str2中的字符
        for (int j = 1; j <= str2.length; j++) {
            // 如果有一个不满足，那么后续的串就都不能拼出str3
            if (str2[j - 1] != str3[j - 1]) {
                break;
            }
            dp[0][j] = 1;
        }
        // 填中间的表
        for (int i = 1; i <= str1.length; i++) {
            for (int j = 1; j <= str2.length; j++) {
                if ((str1[i - 1] == str3[i + j - 1]) && dp[i - 1][j] == 1 || (str2[j - 1] == str3[i + j - 1]) && dp[i][j - 1] == 1) {
                    dp[i][j] = 1;
                }
            }
        }
        return dp[str1.length][str2.length] == 1;
    }
}